Data Structure

Keypoint

Time complexity

• HashMap: O(1)

Q1 Least Recently Cache(LRC)

題目描述： App 需要一個快取機制來存儲下載過的貼圖。記憶體最多只能存 N 張圖。當快取滿了，必須移除「最久沒被使用」的那張圖。請用 Pseudocode 實作 Get(key) 和 Put(key, value)。

參考解答 (Pseudocode)： 解題亮點：這題如果只用 Array 會拿低分。標準解法是 Hash Map + Doubly Linked List。

A1

code
CLASS ImageCache
    PROPERTY capacity: Integer
    PROPERTY cache_map: HashMap<key, Node>
    PROPERTY head: Node
    PROPERTY tail: Node

    // init function
    FUNCTION Init(max_size)
        capacity = max_size
        cache_map = NEW HashMap()
        head = NULL
        tail = NULL
    END FUNCTION

    FUNCTION Get(key)
        IF  key DOES NOT IN cache_map THEN
            RETURN NULL
        END IF

        node = cache_map[key]
        // move this node to the head
        RemoveNode(node)
        AddToHead(node)

        RETURN node.value
    END FUNCTION

    FUNCTION Put(key, image)
        IF cache_map CONTAINS key THEN
            node = cache_map[key]
            node.value = image
            
            RemoveNode(node)
            AddToHead(node)
        ELSE
            new_node = NEW Node(key, image)

            IF cache_map.size >= capacity THEN
                cache_map.REMOVE(tail.key)
                RemoveNode(tail)
            END IF

            AddToHead(new_node)
            cache_map.ADD(key, new_node)
        END IF
    END FUNCTION

    //helpler function
END CLASS

code
// The Node Structure of double linked list
CLASS Node
    PROPERTY key: String
    PROPERTY value: Image
    PROPERTY next: Node
    PROPERTY prev: Node
END CLASS

// Helper Function
/*
Function: AddToHead
Description: Add the node to the head of double link list.
*/
FUNCTION AddToHead(node)
    node.prev = NULL
    node.next = head

    // If the list is not empty
    IF head IS NOT NULL THEN
        head.prev = node
    END IF

    head = node

    // If the list is empty
    IF tail IS NULL THEN
        tail = head
    END IF
END FUNCTION

FUNCTION RemoveNode(node)
    IF node.prev IS NULL THEN
        head = node.next
    ELSE
        prev_node = node.prev
        prev_node.next = node.next
    END IF

    IF node.next IS NULL THEN
        tail = node.prev
    ELSE
        next_node = node.next
        next_node.prev = node.prev
    END IF

    node.prev = NULL
    node.next = NULL
END FUNCTION